package TenkindsOfAlgorithm.dijkstra;

import graph.GraphArray;

/**
 * 一种用于寻找给定的加权图中顶点间 最短路径的算法。Dijkstra
 * 通过选定的被选定顶点，求出出发访问顶点到其他顶点的最短路径。 区别是只求一个。
 * 动画演示
 * https://www.bilibili.com/video/BV1zz4y1m7Nq?from=search&seid=3750679403830173739&spm_id_from=333.337.0.0
 */
public class Dijkstra {
    public static void main(String[] args) {
        String vertexArray[] = {"0","1","2","3","4","5","6","7","8"};
        GraphArray  graph = new GraphArray(vertexArray.length);
        // 把节点添加到图中
        for (String s : vertexArray) {
            graph.insertVertex(s);
        }
        graph.insertEdge("0","1",4);
        graph.insertEdge("0","7",8);
        graph.insertEdge("1","7",11);
        graph.insertEdge("1","2",8);
        graph.insertEdge("7","6",1);
        graph.insertEdge("7","8",7);
        graph.insertEdge("2","8",2);
        graph.insertEdge("2","3",7);
        graph.insertEdge("2","5",4);
        graph.insertEdge("8","6",6);
        graph.insertEdge("6","5",2);
        graph.insertEdge("3","4",9);
        graph.insertEdge("3","5",14);
        graph.insertEdge("5","4",10);
        graph.display();
        graph.dijkstra(0);
    }
}
